package qjc.g_链表;

import com.链表.练习题.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

public class g13_合并K个升序链表 {
    /**
     * 创建一个最小堆（优先队列），按节点的 val 值升序排列,
     * 将每个非空链表的头节点加入堆中,不断从堆中取出最小节点，直到堆为空,
     * 如果该节点还有下一个节点，则将下一个节点加入堆中
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        for (ListNode l : lists) {
            if (l != null) {
                queue.offer(l);
            }
        }
        ListNode s = new ListNode(-1, null);
        ListNode p = s;
        while (!queue.isEmpty()) {
            ListNode node = queue.poll();
            p.next = node;
            p = node;
            if (node.next != null) {
                queue.offer(node.next);
            }
        }
        return s.next;
    }
}
